This invention relates to a three-dimensional data processing device, a three-dimensional data processing method, and a program providing medium for finding a three-dimensional shape of an object. Particularly, this invention relates to a three-dimensional data processing device, a three-dimensional data processing method, and a program providing medium for finding a three-dimensional shape in which a target object is observed from a certain visual point to find distance data from the visual point and then a plurality of distance data from a plurality of different visual points are synthesized to calculate the three-dimensional shape of the whole target object.
There are several techniques for obtaining a three-dimensional shape of an object. The three-dimensional shape measuring methods are roughly classified into active visions and passive visions. The active visions are further classified into a laser technique for emitting a laser beam or an ultrasonic wave and measuring the quantity of reflected light from the object and the reaching time of the laser beam or ultrasonic wave to extract depth information, a pattern projection method for estimating the object shape from image information such as geometric deformation of the object surface pattern by using a special pattern light source such as a slit light, a method for forming contour lines using moire fringes by optical processing and thus obtaining three-dimensional information, and other methods. On the other hand, the passive visions are classified into a single-view stereoscopic vision for estimating three-dimensional information from one image, a stereo method for estimating depth information of each pixel using trigonometric principles, and other methods.
The distance information of the measuring object obtained by using the above-described laser technique or the stereo method is data indicating the surface shape of the measuring object and is called range data. The range data is aggregate data of distance data of measuring points at sample points obtained by using the laser technique or the stereo method.
Shooting data such as the color of the surface of the measuring object, similar to the data observed with the naked eye, is called texture data. The processing to correspond the range data to the texture data is referred to as texture mapping. By the texture mapping, a three-dimensional model of the measuring object is generated.
Generally, in one measurement, only the range data of the measuring object from one direction set as a measuring point is obtained. If a three-dimensional shape of the whole object is to be found, the processing to register and synthesize the range data from a plurality of measuring points is necessary. The same is true of the texture data.
To synthesize a plurality of range data, for example, the measuring object is set on a rotary table and a correspondence of the shooting direction to the rotation angle of the rotary table is made to obtain a plurality of range data. Thus, a plurality of range data or a plurality of texture data can be synthesized on the basis of the rotation angle of the rotary table. However, with respect to large objects that cannot be set on the rotary table, for example, a house, a building, a statue, natural features and the like, it is difficult to synthesize a plurality of range data by such a technique.
It is common to carry out the processing to set a measuring area so that each one of a plurality of range data has an overlap area with the other range data, and calculate the correlation of the distance data in the overlap area of the respective range data so as to find a position of high correlation as a position for synthesizing a plurality of range data. FIGS. 1A and 1B show an example of range data synthesis processing based on the correlation of range data.
It is assumed that registration and synthesis of range data from two measuring points of two range data measuring devices 102, 103 are carried out with respect to a measuring object 101 shown in FIG. 1A. The range data obtained by the range data measuring devices 102, 103 are shown in FIG. 1B. In FIG. 1B, to simplify the description, the range data is considered to be linear data extending on the X-axis cut on a certain plane. In this case, one of the range data is fixed and the other is shifted on the X-axis. Then, a point of the highest correlation in the overlap area of the two range data is found, thus carrying out the processing to register the two range data. In the case where the shape of the surface of the measuring object is characteristic, that is, uneven, as shown in FIGS. 1A and 1B, it is relatively easy to find the overlap area of the adjacent different range data from the correlation of the range data.
The registration algorithm in the overlap area of the different range data is carried out, for example, by the processing to find a corresponding position of the range data which minimizes the following equation (1).                               ɛ          2                =                                            ∑              i                        ⁢                                          D                ⁡                                  (                                                            x                      ⁡                                              (                        i                        )                                                              ,                                          y                      ⁡                                              (                        i                        )                                                                              )                                            2                                =                                    ∑              i                        ⁢                                                                                                (                                                                  R                        ⁢                                                                                                   ⁢                                                  x                          ⁡                                                      (                            i                            )                                                                                              +                      t                                        )                                    -                                      y                    ⁡                                          (                      i                      )                                                                                                  2                                                          (        1        )            
In this equation, x(i) and y(i) represent distance data values of range data x and range data y at a sample point (i). R represents a rotation matrix and t represents a translational vector. The processing to minimize the equation (1) is carried out by fixing one of the range data and changing the shift quantity R, t of the other range data. That is, the processing to calculate the shift quantity R, t for providing the minimum value of the equation (1) is carried out.
Many techniques of the range data registration processing are based on the algorithm developed by P. J. Besl (for example, P. J. Besl, N. D. Mckey, A Method of Registration of 3-D Shapes, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.14, No.2, 1992, pp.239-256). As an application of this algorithm, there is an example constructed by Z. Zhang (Z. Zhang, Iterative Point Matching for Registration of Free-form Curves and Surface, International Journal of Computer Vision, Vol. 13, No.2, 1994, pp. 119-152). This basic algorithm is called ICP (iterative closest point). According to ICP, the closest points of overlapping range data are used as corresponding points and the shift quantity R, t is repeatedly calculated to minimize in the above-described equation, thus carrying out registration between the range data. However, since this method is only applicable to range data having an overlap area and the closest points are simply determined as the corresponding points, erroneous correspondence easily occurs in the case of less characteristic shapes.
Moreover, the above-described method is adapted for registration between two adjacent range data. If the registration processing of three or more range data is sequentially carried out by using the above-described method, registration errors are sequentially propagated and accumulated at the terminal end. If an object is scanned from a plurality of directions to shoot (measure) range data of the whole object and registration of the range data is sequentially carried out, errors are accumulated, and in the worst case, the data might not be closed.
As a method for eliminating such problems, a technique of simultaneously registering a plurality of range data is considered. A typical technique is proposed by Neugebauter (Peter J. Neugebauter, Reconstruction of Real-World Objects Via Simultaneous Registration and Robust Combination of Multiple Range Images, International Journal of Shape Modeling, Vol.3, Nos.1&2, June 1997, pp.71-90). In this technique, the shift quantity R, t between the respective ranges is found so that errors in all the overlapping range data are reduced simultaneously. A corresponding point is considered to be a point where a straight line parallel to the shooting direction passing through a point on one range data intersects the other range data. In this technique, however, registration between the range data is carried out by using only the characteristics of the surface shape obtained from the range data. Therefore, in the case where an object, like a canister, which has a uniform surface and is difficult to register on the basis of the surface shape is used as a measuring object, registration between a plurality of range data is difficult.
For example, when range data of a measuring object 201 as shown in FIG. 2A are obtained from different measuring points and the registration processing of the range data is to be carried out on the basis of the correlation of distance information (surface shape) obtained from the range data, the surface of the measuring object has no characteristic unevenness and therefore the correlation value is hardly changed by shifting one of the range data, as shown in FIG. 2B. Therefore, it is difficult to carry out registration of the overlap area of the range data on the basis of the correlation of the range data and to calculate the accurate surface shape of the whole measuring object.
For registration of the entire circumference as a technique for compensating the difficulty in the above-described registration processing with the range data alone, a method using a boundary surface of the color of the texture is proposed (Tomoyuki Ishikawa, Masaki Otsuki, Yukio Sato, Integration of a Plurality of Range Data Using Color Boundary Portion, Computer Vision and Image Media 110-11, 1998, 3, 19). According to this method, when there is a clear difference (boundary) of color on the surface of an object, the corresponding point is corrected using the boundary as a clue. However, when there is no clear boundary on a measuring object, this method cannot be used.